Unless otherwise indicated herein, the materials described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Coding for rewriting is a technology used for flash memories. Coding has the potential to substantially increase the longevity, speed, and power efficiency of flash memories. Coding for rewriting has been proposed recently. See, e.g. V. Bohossian, A. Jiang, and J. Bruck, “Buffer coding for asymmetric multi-level memory,” in Proc. IEEE Internatio. Nal Symposium on Information Theory, June 2007, pp. 1186-1190, and A. Jiang, V. Bohossian, and J. Bruck, “Floating codes for joint information storage in write asymmetric memories,” in Proc. IEEE International Symposium on Information Theory, June 2007, pp. 1166-1170, which are incorporated herein by reference. Since the time coding was initially proposed, many works have appeared in this area. See, e.g. Y. Wu, “Low complexity codes for writing a write-once memory twice,” in Proc. IEEE International Symposium on Information Theory, June 2010, pp. 1928-1932, Y. Wu and A. Jiang, “Position modulation code for rewriting write-once memories,” IEEE Trans. Inf. Theor., vol. 57, no. 6, pp. 3692-3697, June 2011, E. Yaakobi, S. Kayser, P. H. Siegel, A. Vardy, and J. K. Wolf, “Codes for write-once memories,” IEEE Trans. Inf. Theor., vol. 58, no. 9, pp. 5985-5999, September 2012, and E. Yaakobi, S. Kayser, P. Siegel, A. Vardy, and J. Wolf, “Efficient two-write wom-codes,” in Proc. IEEE Information Theory Workshop, September 2010, pp. 1-5, which are incorporated herein by reference.
A model for rewriting is a write-once memory (WOM) model. See. e.g. R. L. Rivest and A. Shamir, “How to reuse a write-once memory,” Information and Control, vol. 55, no. 1-3, pp. 1-19, 1982, which is incorporated herein by reference. In the WOM model, a set of binary cells are used to store data, and the cell charge levels are increased when the data are rewritten. For flash memories, this constraint implies that the rewriting operation may delay the expensive block erasure, which leads to better preservation of cell quality and higher writing performance.
There have been many techniques for the design of WOM codes. They include linear code, tabular code, codes based on projective geometry, coset coding, etc. See, e.g. G. Cohen, P. Godlewski, and F. Merkx, “Linear binary code for write-once memories,” IEEE Trans. Inf. Theor., vol. 32, no. 5, pp. 697-700, September 1986, Merkx, “Womcodes constructed with projective geometries” Traitement du Signal, vol. 1, no. 2-2, pp. 227-231, 1984, and R. L. Rivest and A. Shamir, “How to reuse a write-once memory,” Information and Control, vol. 55, no. 1-3, pp. 1-19, 1982, which are incorporated herein by reference. Codes with substantially higher rates were discovered in recent years. See, e.g. V. Bohossian, A. Jiang, and J. Bruck, “Buffer coding for asymmetric multi-level memory,” in Proc. IEEE International Symposium on Information Theory, June 2007, pp. 1186-1190, and A. Jiang, V. Bohossian, and J. Bruck, “Floating codes for joint information storage in write asymmetric memories,” in Proc. IEEE International Symposium on Information Theory, June 2007, pp. 1166-1170, which are incorporated herein by references. Since the time such coding was initially proposed, many works have appeared in this area. See, e.g. Y. Wu, “Low complexity codes for writing a write-once memory twice,” in Proc. IEEE International Symposium on Information Theory, June 2010, pp. 1928-1 2, E. Yaakobi, S. Kayser, P. H. Siegel, A. Vardy, and J. K. Wolf, “Codes for write-once memories,” IEEE Trans. Inf. Theor., vol. 58, no. 9, pp. 5985-5999, September 2012, which are incorporated herein by reference. In 2012, WOM codes that achieved capacity were discovered by Shpilka et al. and Burshtein et al. See, e.g. A. Shpilka, “Capacity achieving multiwrite wom codes,” CoRR, vol. abs/1207.1128, 2012, “Capacity achieving two-write wom codes,” in LATIN 2012: Theoretical Informatics, ser. Lecture Notes in Computer Science, vol. 7256. Springer Berlin Heidelberg, 2012, pp. 631-642, E. Yaakobi and A. Shpilka, “High sum-rate three-write and non-binary wom codes,” in Proc. IEEE International Symposium on Information Theory, July 2012, pp. 1386-1390, and D. Burshtein and A. Strugatski, “Polar write once memory codes,” in Proc. IEEE International Symposium on Information Theory, July 2012, pp. 1972-1976, which are incorporated herein by reference. The latter code used a construction based on polar coding.
Compared to the large amount of work on WOM codes, the work on WOM codes that also correct errors has been much more limited. Existing works are mainly on correcting a few errors (for example, 1, 2, or 3 errors). See, e.g. E. Yaakobi, P. Siegel, A. Vardy, and J. Wolf, “Multiple error-correcting wom-codes,” IEEE Trans. Inf. Theor., vol. 58, no. 4, pp. 2220-2230, April 2012, and G. Zemor and G. D. Cohen, “Error-correcting wom-codes,” IEEE Trans. Inf. Theor., vol. 37, no. 3, pp. 730-734, May 1991, which are incorporated herein by reference.